package primalgorithms.dynamicplanning;

public class _01ClimbStairs {
    public static int climbStairs(int n) {
        //  先写递推公式
        //  f(n) = f(n-1) + f(n-2)
        //  f(1) = 1 , f(2) = 2
        if (n == 1){
            return 1;
        }
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3;i < n+1;i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
    /** 公式法
     *  public static int climbStairs(int n) {
     *      double sqrt = Math.sqrt(5);
     *      return (int) ((Math.pow((1 + sqrt) / 2, n + 1) - Math.pow((1 - sqrt) / 2, n + 1)) / sqrt);
     *  }
     */

    /** 递归法：效率较低
     *  public static int climbStairs(int n) {
     *      if (n == 1 || n == 2){
     *          return n;
     *      }
     *      return climbStairs(n-1)+climbStairs(n-2);
     *  }
     */

}
